﻿// 4251. Nya图最短路.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://www.acwing.com/problem/content/4254/


Nya 图是一种分层的无向图。

图中共有 N
 个节点，每个节点都处于某一层当中。

层与层之间存在阶梯。

利用阶梯可以从任意一层的任意一个节点移动至其相邻层（上一层或下一层）的任意一个节点。

每次利用阶梯进行移动都需要花费固定的成本 C
。

此外，还有 M
 个点对之间存在额外边。

如果点 u
 和点 v
 之间存在额外边，则可以通过额外边在点 u
 和点 v
 之间进行双向移动。

每次利用额外边进行移动都需要花费一定的成本，不同额外边的花费可能不同。

请你计算从点 1
 移动至点 N
 所需花费的最低成本。

输入格式
第一行包含一个整数 T
，表示共有 T
 组测试数据。

每组数据第一行包含三个整数 N,M,C
。

第二行包含 N
 个整数 li
，表示每个点所在的具体层数。

接下来 M
 行，每行包含三个整数 u,v,w
，表示点 u
 和点 v
 之间存在一条额外边，成本为 w
。

输出格式
每组数据输出一行答案，具体格式为 Case #x: y，其中 x
 为组别编号（从 1
 开始），y
 为所需花费的最低成本。如果无法到达点 N
，则为 −1
。

数据范围
1≤T≤20
,
0≤N,M≤105
,
1≤C≤103
,
1≤li≤N
,
1≤u,v≤N
,
u≠v
,
1≤w≤104
。

输入样例：
2
3 3 3
1 3 2
1 2 1
2 3 1
1 3 3
3 3 3
1 3 2
1 2 2
2 3 2
1 3 4
输出样例：
Case #1: 2
Case #2: 3
*/
int main()
{
    std::cout << "Hello World!\n";
}

 